class Solution {
    /*
     * 对称二叉树
     * DFS
     *
     * */
    public boolean isSymmetric(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        if(p.val == q.val){
            return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
        }
        return false;
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    /*
     * BFS
     *
     * */
    public static boolean isSym(List<TreeNode> list){
        int left = 0;
        int right = list.size()-1;
        while(left < right){
            if(list.get(left) == null && list.get(right) != null){
                return false;
            }
            if(list.get(left) != null && list.get(right) == null){
                return false;
            }
            if(list.get(left) != null && list != null) {
                if (list.get(left).val != list.get(right).val) {
                    return false;
                }
            }
            left++;
            right--;
        }
        return true;
    }
    public static boolean isSymmetric2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<TreeNode> list = new ArrayList<>();
            while(size > 0){
                TreeNode node = queue.poll();
                if(node != null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
                list.add(node);
                size--;
            }
            if(!isSym(list)){
                return false;
            }
        }
        return true;
    }
    /*
     * BFS
     * 改变一下入队的顺序，出队是就可以很好的判断喽
     *
     * */
    public static boolean isSymmetric3(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode p = queue.poll();
            TreeNode q = queue.poll();
            if(p == null && q == null){
                continue;
            }
            if(p == null || q == null){
                return false;
            }
            if(p.val != q.val){
                return false;
            }

            queue.offer(p.left);
            queue.offer(q.right);

            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;
    }
}